package lz77;

import java.io.BufferedInputStream;
import java.io.EOFException;
import java.io.InputStream;
import java.io.IOException;
import lz77.util.LoopArray;

/**
 * LZ77 -algoritmissa käytettävä puskuri
 * 
 * @author ossi
 * 
 */
public class Buffer {

	private LoopArray bufferContents;

	private InputStream inStream;
	/**
	 * Puskurin keskikohta, eli missä puskuri "loppuu" ja sisääntuleva data
	 * alkaa
	 */
	public final int bufferEnd;
	/**
	 * Pitää kirjaa kuinka monta käsiteltävää merkkiä puskurissa on jäljellä
	 * streamin loppumisen jälkeen
	 */
	private int endCounter;

	public final int length;

	public Buffer(InputStream in, char size) throws IOException {
		bufferContents = new LoopArray(size);
		length = bufferContents.length;
		bufferEnd = size / 2;

		endCounter = bufferEnd;

		inStream = new BufferedInputStream(in);

		// täytetään puskuri puolilleen
		for (int i = bufferEnd; i < bufferContents.length; i++) {
			next();
		}

	}

	/**
	 * Syöttää seuraavan tavun streamista puskuriin.
	 * 
	 * @return syötetty tavu
	 * @throws IOException
	 *             EOFException jos tiedosto loppuu
	 */
	public byte next() throws IOException {

		byte nextByte = 0;
		int input = inStream.read();

		if (input == -1) { // stream lopussa
			endCounter++;
			if (endCounter >= bufferContents.length) {
				throw new EOFException(); // valmista tuli
			}
			nextByte = -1;
		} else {
			nextByte = (byte) input;
		}

		bufferContents.push(nextByte);

		return nextByte;
	}

	/**
	 * KMP -haku puskurista
	 * 
	 * @param needle
	 *            Haettava merkkijono
	 * @return taulukko, jossa 0 -alkio kertoo paikan josta merkkijono
	 *         löydettiin, ja 1 -alkio kertoo montako merkkiä siitä löydettiin
	 */
	public char[] kmp_find(byte[] needle) {
		char m = 0; // paikka puskurissa
		char i = 0; // paikka etsittävässä merkkijonossa
		char len = 0, pos = 0;
		int[] T = kmp_table(needle);

		while (m + i < (bufferEnd + i)) { // ei olla etsittävän alueen lopussa
			if (needle[i] == bufferContents.get(m + i)) {
				if (i == needle.length - 1) { // löytyi merkkijono sellaisenaan
					return new char[] { m, (char) (i + 1) };
				}
				i++;

				if (i > len) { // pisin löydetty etuliite
					len = i;
					pos = m;
				}

			} else {
				// siirrytään taulukon osoittaman määrän askeleita
				// taaksepäin
				m = (char) (m + i - T[i]);
				if (T[i] > -1) {
					i = (char) T[i];
				} else {
					i = 0;
				}
			}
		}
		return new char[] { pos, len };
	}

	/**
	 * Laksee KMP -haussa käytetyn "hyppytaulun"
	 * 
	 * @param word
	 *            Etsittävänä oleva merkkijono
	 * @return KMP -taulukko
	 */
	private int[] kmp_table(byte[] word) {
		int[] T = new int[word.length];

		// algoritmi antaisi väärät arvot kahdelle ensimmäiselle alkiolle
		T[0] = -1;
		T[1] = 0;

		int pos = 2; // T:n indeksi jolle lasketaan arvoa
		int cnd = 0; // mahdollisen alkuliitteen seuraavan merkin indeksi

		while (pos < word.length) {
			if (word[pos - 1] == word[cnd]) { // alkuliitteen seuraava merkki
												// täsmää
				cnd++; // siirrytään seuraavaan verrattavaan merkkiin
				T[pos] = cnd;
				pos++;

			} else if (cnd > 0) {
				// alkuliiteen jokin muu kuin ensimmäinen merkki ei täsmää
				cnd = T[cnd]; 
			} else { // ensimmäinen merkki ei täsmää
				T[pos] = 0;
				pos++; 
			}
		}
		return T;
	}

	/**
	 * Palauttaa seuraavaksi käsiteltävän tavujonon
	 * 
	 * @return Seuraavaksi käsiteltävä tavujono
	 */
	public byte[] getNextString() {
		return bufferContents.getSlice(bufferEnd, bufferContents.length
				- bufferEnd);
	}

	public byte get(int i) {
		return bufferContents.get(i);
	}
}
